Sử sách không cho biết năm sinh của Thư Cừ Mục Kiền nay tên mẫu thân của ông, ông là con trai thứ ba của Thư Cừ Mông Tốn. Sự kiện đầu tiên trong sử sách nhắc đến ông là vào năm 420, sau khi Thư Cừ Mông Tốn tiêu diệt nước Tây Lương kình định và chiếm được kinh thành Tửu Tuyền (酒泉, nay thuộc Tửu Tuyền, Cam Túc) của nước này, Thư Cừ Mông Tốn đã để ông làm thái thú của quận Tửu Tuyền và gả Lý Kính Thụ (李敬受), vương hậu của vua Lý Hâm (Lý Hâm lúc này đã chết), cho ông.

Thư Cừ Mục Kiền chưa từng được phụ thân mong muốn là người kế vị, cha ông ban đầu lập anh cả Thư Cừ Chính Đức (沮渠政德) làm thế tử vào năm 413. Sau khi Thư Cừ Chính Đức chết khi đánh quân Nhu Nhiên vào năm 423, Thư Cừ Mông Tốn đã lệnh một người anh trai khác của Thư Cừ Mục Kiền là Thư Cừ Hưng Quốc (沮渠興國) làm thế tử. Sau khi Thư Cừ Hưng Quốc bị vua Khất Phục Mộ Mạt của Tây Tần bắt được và giữ lại vào năm 429, và Thư Cừ Mông Tốn thất bại khi tìm cách chuộc Thư Cừ Hưng Quốc, ông ta đã lập một em trai cùng mẹ với Thư Cừ Mục Kiền là Thư Cừ Bồ Đề (沮渠菩提) làm thế tử. Tuy nhiên, khi Thư Cừ Mông Tốn lâm bệnh vào năm 433, các quan lại và quý tộc đã cho rằng Bồ Đề còn quá trẻ để kế vị, vì thế họ đã phế truất Thư Cừ Bồ Đề và đưa Thư Cừ Mục Kiền, người được coi là mẫn cán và có lòng tốt, làm thế tử. Thư Cừ Mông Tốn qua đời ngay sau đó, và Thư Cừ Mục Kiền đã lên kế vị. Ông lập con trai mình là Thư Cừ Phong Đàn (沮渠封壇) làm thế tử.